The Luleå algorithm of

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, designed by , is a technique for storing and searching

internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...

routing table In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with tho ...

s efficiently. It is named after the

Luleå University of Technology Luleå University of Technology is a Public Research University in Norrbotten County, Sweden. The university has four campuses located in the Arctic Region in the cities of Luleå, Kiruna, Skellefteå, and Piteå. With more than 19,000 students a ...

, the home institute/university of the technique's authors. The name of the algorithm does not appear in the original paper describing it, but was used in a message from

Craig Partridge Dr. Craig Partridge is an American computer scientist, best known for his contributions to the technical development of the Internet. Partridge graduated in 1979 from Woodrow Wilson High School in Washington D.C. He received his A.B. in history i ...

to the

Internet Engineering Task Force The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...

describing that paper prior to its publication.second Europe trip for IETFers...
, Craig Partridge to IETF, May 1, 1997. The key task to be performed in internet routing is to match a given

IPv4 Internet Protocol version 4 (IPv4) is the fourth version of the Internet Protocol (IP). It is one of the core protocols of standards-based internetworking methods in the Internet and other packet-switched networks. IPv4 was the first version de ...

address An address is a collection of information, presented in a mostly fixed format, used to give the location of a building, apartment, or other structure or a plot of land, generally using political boundaries and street names as references, along w ...

(viewed as a sequence of 32 bits) to the longest

prefix A prefix is an affix which is placed before the Word stem, stem of a word. Adding it to the beginning of one word changes it into another word. For example, when the prefix ''un-'' is added to the word ''happy'', it creates the word ''unhappy'' ...

of the address for which routing information is available. This prefix matching problem may be solved by a

trie In computer science, a trie, also called digital tree or prefix tree, is a type of ''k''-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes def ...

, but trie structures use a significant amount of space (a

node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...

for each bit of each address) and searching them requires traversing a sequence of nodes with length proportional to the number of bits in the address. The Luleå algorithm shortcuts this process by storing only the nodes at three levels of the trie structure, rather than storing the entire trie. Before building the Luleå trie, the routing table entries need to be preprocessed. Any bigger prefix that overlaps a smaller prefix must be repeatedly split into smaller prefixes, and only the split prefixes which does not overlap the smaller prefix is kept. It is also required that the prefix tree is complete. If there is no routing table entries for the entire address space, it must be completed by adding dummy entries, which only carries the information that no route is present for that range. This enables the simplified lookup in the Luleå trie (). The main advantage of the Luleå algorithm for the routing task is that it uses very little memory, averaging 4–5 bytes per entry for large routing tables. This small memory footprint often allows the entire data structure to fit into the routing processor's cache, speeding operations. However, it has the disadvantage that it cannot be modified easily: small changes to the routing table may require most or all of the data structure to be reconstructed. A modern home-computer (PC) has enough hardware/memory to perform the algorithm.

First level

The first level of the data structure consists of * A

bit vector A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level pa ...

consisting of 2¹⁶ = 65,536 bits, with one entry for each 16-bit prefix of an

address. A bit in this table is set to one if there is routing information associated with that prefix or with a longer sequence beginning with that prefix, or if the given prefix is the first one associated with routing information at some higher level of the trie; otherwise it is set to zero. * An array of 16-bit

words A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...

for each nonzero bit in the bit vector. Each

datum In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted. ...

either supplies an index that points to the second-level data structure object for the corresponding prefix, or supplies the routing information for that prefix directly. * An array of "base indexes", one for each consecutive subsequence of 64 bits in the bit vector, pointing to the first datum associated with a nonzero bit in that subsequence. * An array of "code words", one for each consecutive subsequence of 16 bits in the bit vector. Each code word is 16 bits, and consists of a 10-bit "value" and a 6-bit "offset". The sum of the offset and the associated base index gives a pointer to the first datum associated with a nonzero bit in the given 16-bit subsequence. The 10-bit value gives an index into a "maptable" from which the precise position of the appropriate datum can be found. * A maptable. Because the prefix tree is required to be complete, there can only exist a limited amount of possible 16-bit bitmask values in the bit vector, 678. The maptable rows correspond to these 678 16-bit combinations, and columns the number of set bits in the bitmask at the bit location corresponding to the column, minus 1. So column 6 for the bitmask 1010101010101010 would have the value 2. The maptable is constant for any routing table contents. To look up the datum for a given address ''x'' in the first level of the data structure, the Luleå algorithm computes three values: #the base index at the position in the base index array indexed by the first 10 bits of ''x'' #the offset at the position in the code word array indexed by the first 12 bits of ''x'' #the value in maptable 'y''''z''], where ''y'' is the maptable index from the code word array and ''z'' is bits 13–16 of ''x'' The sum of these three values provides the index to use for ''x'' in the array of items.

Second and third levels

The second and third levels of the data structure are structured similarly to each other; in each of these levels the Luleå algorithm must perform prefix matching on 8-bit quantities (bits 17–24 and 25–32 of the address, respectively). The data structure is structured in "chunks", each of which allows performing this prefix matching task on some subsequence of the address space; the data items from the first level data structure point to these chunks. If there are few enough different pieces of routing information associated with a chunk, the chunk just stores the list of these routes, and searches through them by a single step of

binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...

followed by a

sequential search In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at ...

. Otherwise, an indexing technique analogous to that of the first level is applied.

Notes

References

*. *. *. *. {{DEFAULTSORT:Lulea Algorithm Internet architecture Routing software Networking algorithms Routing algorithms Luleå University of Technology